//
// Created by francklinson on 2021/8/31 AT 16:06.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>

using namespace std;

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>> &bookings, int n) {
        // 暴力
        vector<int> flights(n, 0);
        for (int i = 0; i < bookings.size(); ++i) {
            int left = bookings[i][0];
            int right = bookings[i][1];
            int num = bookings[i][2];
            for (int j = left - 1; j <= right - 1; ++j) {
                flights[j] += num;
            }
        }
        return flights;
        // 超时
    }
};

class Solution2 { // 题解 差分数组+前缀和
public:
    /**
     * 差分数组的性质是：对nums的[l,r]区间内的每个数给一个增量d,等效于对nums[l]+d,nums[r+1]-d.
     * 差分数组转换为结果是，是采用前缀和的形式
     * @param bookings
     * @param n
     * @return
     */
    vector<int> corpFlightBookings(vector<vector<int>> &bookings, int n) {
        vector<int> nums(n);
        for (auto &booking: bookings) {
            nums[booking[0] - 1] += booking[2];
            if (booking[1] < n) {
                nums[booking[1]] -= booking[2];
            }
        }
        for (int i = 1; i < n; i++) {
            nums[i] += nums[i - 1];
        }
        return nums;
    }
};

int main() {
    vector<vector<int>> bookings{{1, 2, 10},
                                 {2, 3, 20},
                                 {2, 5, 25}};
    Solution2 solution;
    vector<int> ans = solution.corpFlightBookings(bookings, 5);
    for (auto &x: ans) {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

